package array;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * Created by fengliejv on 2017/10/2.
 */

public class NextGreaterElement496 {

//单调栈
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> deque = new LinkedList<>();
        for (int i = nums2.length-1; i >= 0 ; i--) {
            if(deque.isEmpty()){
                deque.push(nums2[i]);
                map.put(nums2[i],-1);
                continue;
            }
            while (!deque.isEmpty()&&deque.peek()<nums2[i]){
                deque.pop();
            }
            map.put(nums2[i],deque.isEmpty()?-1:deque.peek());
            deque.push(nums2[i]);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }


//暴力法
//    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
//        for (int i = 0; i < nums2.length; i++) {
//            this.setMap(i,nums2,map);
//        }
//        int[] val = new int[nums1.length];
//        for (int i = 0; i < nums1.length ; i++) {
//            val[i]=map.get(nums1[i]);
//        }
//        return val;
//    }
//
//    private void setMap(int i,int[] nums2,HashMap map){
//        if(i==nums2.length-1){
//            map.put(nums2[i],-1);
//            return;
//        }
//        for (int j = i+1; j <nums2.length ; j++) {
//            if(nums2[i]<nums2[j]){
//                map.put(nums2[i],nums2[j]);
//                return;
//            }
//            if(j==nums2.length-1){
//                map.put(nums2[i],-1);
//            }
//        }
//    }
}
